import java.util.Scanner;
import java.util.Stack;

/**
 * @Author @fiber-cloud
 * @Date 2025/8/3 9:04
 * 栈相关题目
 */
public class Test {
    //括号匹配问题
    public boolean isValid(String s) {

        Stack<Character> stack = new Stack<>();

        for (int i = 0; i < s.length(); i++) {
            char ch = s.charAt(i);
            //左括号放入栈
            if (ch == '(' || ch == '[' || ch == '{'){
                stack.push(ch);
            }else {
                //遇到了右括号，但此时栈为空
                if (stack.empty()){
                    return false;
                }

                char ch2 = stack.peek();
                if (ch2 == '[' && ch == ']' || ch2 == '{' && ch == '}' || ch2 == '(' && ch == ')'){
                    stack.pop();//匹配弹出
                }else {
                    return false;
                }
            }
        }
        //如果遍历完了，栈中还有元素，说明没有匹配完
        if (!stack.empty()){
            return false;
        }
        return true;
    }


    //出栈入栈次序匹配
    public boolean IsPopOrder (int[] pushV, int[] popV) {
        Stack<Integer> stack = new Stack<>();
        int j = 0;//遍历popV数组
        // 1.i下标遍历v数组，直接入栈
        for (int i = 0; i < pushV.length; i++) {
            stack.push(pushV[i]);

            // 2.入栈后判断j下标是否为当前值
            // 3.如果是，出栈，j++，弹出栈顶元素；弹出后判断栈顶是否与j一样，不一样i++

            //Integer是有范围的，如果在范围内，可以用== 但如果不在范围内要换成equals
            while (j<popV.length && !stack.empty() && stack.peek().equals(popV[j]) ){
                stack.pop();
                j++;
            }
            // 4.如果不是，则继续i++
        }
        return stack.empty();
    }
}
